SherbyNet - /page/wikibook/entry.mu

Micron Document

Upper set

14.4 KB · ⇊ 10 parts · ⤓ Micron 14.4 KB · ⤓ HTML 90.1 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X)cite-ref-footnotedoleckimynard201627-29-1-0[1] of a partially ordered set ( X , ≤ ≤ ) {\displaystyle (X,\leq )} is a subset S ⊆ ⊆ X {\displaystyle S\subseteq X} with the following property: if s is in S and if x in X is larger than s (that is, if s < x {\displaystyle s<x} ), then x is in S. In other words, this means that any x element of X that is ≥ ≥ {\displaystyle \,\geq \,} to some element of S is necessarily also an element of S. The term lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal) is defined similarly as being a subset S of X with the property that any element x of X that is ≤ ≤ {\displaystyle \,\leq \,} to some element of S is necessarily also an element of S.

Contents

• Definition

• Properties

• Upper closure and lower closure

• Ordinal numbers

• See also

• References

Definition

Let ( X , ≤ ≤ ) {\displaystyle (X,\leq )} be a preordered set. An upper set in X {\displaystyle X} (also called an upward closed set, up set, increasing set, or an isotone set)cite-ref-footnotedoleckimynard201627-29-1-1[1] is a subset U ⊆ ⊆ X {\displaystyle U\subseteq X} that is "closed under going up", in the sense that

for all u ∈ ∈ U {\displaystyle u\in U} and all x ∈ ∈ X , {\displaystyle x\in X,} if u ≤ ≤ x {\displaystyle u\leq x} then x ∈ ∈ U . {\displaystyle x\in U.}

The dual notion is a lower set (also called a downward closed set, down set, decreasing set, initial segment, or a semi-ideal), which is a subset L ⊆ ⊆ X {\displaystyle L\subseteq X} that is "closed under going down", in the sense that

for all l ∈ ∈ L {\displaystyle l\in L} and all x ∈ ∈ X , {\displaystyle x\in X,} if x ≤ ≤ l {\displaystyle x\leq l} then x ∈ ∈ L . {\displaystyle x\in L.}

The terms order ideal or ideal are sometimes used as synonyms for lower set.cite-ref-dp-2-0[2]cite-ref-3[3]cite-ref-4[4] This choice of terminology fails to reflect the notion of an ideal of a lattice because a lower set of a lattice is not necessarily a sublattice.cite-ref-dp-2-1[2]

Properties

• Every preordered set is an upper set of itself.

• The intersection and the union of any family of upper sets is again an upper set.

• The complement of any upper set is a lower set, and vice versa.

• Given a partially ordered set ( X , ≤ ≤ ) , {\displaystyle (X,\leq ),} the family of upper sets of X {\displaystyle X} ordered with the inclusion relation is a complete lattice, the upper set lattice.

• Given an arbitrary subset Y {\displaystyle Y} of a partially ordered set X , {\displaystyle X,} the smallest upper set containing Y {\displaystyle Y} is denoted using an up arrow as ↑ ↑ Y {\displaystyle \uparrow Y} (see upper closure and lower closure).

• Dually, the smallest lower set containing Y {\displaystyle Y} is denoted using a down arrow as ↓ ↓ Y . {\displaystyle \downarrow Y.}

• A lower set is called principal if it is of the form ↓ ↓ { x } {\displaystyle \downarrow \{x\}} where x {\displaystyle x} is an element of X . {\displaystyle X.}

• Every lower set Y {\displaystyle Y} of a finite partially ordered set X {\displaystyle X} is equal to the smallest lower set containing all maximal elements of Y {\displaystyle Y}

• ↓ ↓ Y =↓ ↓ Max ⁡ ⁡ ( Y ) {\displaystyle \downarrow Y=\downarrow \operatorname {Max} (Y)} where Max ⁡ ⁡ ( Y ) {\displaystyle \operatorname {Max} (Y)} denotes the set containing the maximal elements of Y . {\displaystyle Y.}

• A directed lower set is called an order ideal.

• For partial orders satisfying the descending chain condition, antichains and upper sets are in one-to-one correspondence via the following bijections: map each antichain to its upper closure (see below); conversely, map each upper set to the set of its minimal elements. This correspondence does not hold for more general partial orders; for example the sets of real numbers { x ∈ ∈ R : x > 0 } {\displaystyle \{x\in \mathbb {R} :x>0\}} and { x ∈ ∈ R : x > 1 } {\displaystyle \{x\in \mathbb {R} :x>1\}} are both mapped to the empty antichain.

Upper closure and lower closure

Given an element x {\displaystyle x} of a partially ordered set ( X , ≤ ≤ ) , {\displaystyle (X,\leq ),} the upper closure or upward closure of x , {\displaystyle x,} denoted by x ↑ ↑ X , {\displaystyle x^{\uparrow X},} x ↑ ↑ , {\displaystyle x^{\uparrow },} or ↑ ↑ x , {\displaystyle \uparrow \!x,} is defined by x ↑ ↑ X = ↑ ↑ x = { u ∈ ∈ X : x ≤ ≤ u } {\displaystyle x^{\uparrow X}=\;\uparrow \!x=\{u\in X:x\leq u\}} while the lower closure or downward closure of x {\displaystyle x} , denoted by x ↓ ↓ X , {\displaystyle x^{\downarrow X},} x ↓ ↓ , {\displaystyle x^{\downarrow },} or ↓ ↓ x , {\displaystyle \downarrow \!x,} is defined by x ↓ ↓ X = ↓ ↓ x = { l ∈ ∈ X : l ≤ ≤ x } . {\displaystyle x^{\downarrow X}=\;\downarrow \!x=\{l\in X:l\leq x\}.}

The sets ↑ ↑ x {\displaystyle \uparrow \!x} and ↓ ↓ x {\displaystyle \downarrow \!x} are, respectively, the smallest upper and lower sets containing x {\displaystyle x} as an element. More generally, given a subset A ⊆ ⊆ X , {\displaystyle A\subseteq X,} define the upper/upward closure and the lower/downward closure of A , {\displaystyle A,} denoted by A ↑ ↑ X {\displaystyle A^{\uparrow X}} and A ↓ ↓ X {\displaystyle A^{\downarrow X}} respectively, as A ↑ ↑ X = A ↑ ↑ = ⋃ ⋃ a ∈ ∈ A ↑ ↑ a {\displaystyle A^{\uparrow X}=A^{\uparrow }=\bigcup _{a\in A}\uparrow \!a} and A ↓ ↓ X = A ↓ ↓ = ⋃ ⋃ a ∈ ∈ A ↓ ↓ a . {\displaystyle A^{\downarrow X}=A^{\downarrow }=\bigcup _{a\in A}\downarrow \!a.}

In this way, ↑ ↑ x =↑ ↑ { x } {\displaystyle \uparrow x=\uparrow \{x\}} and ↓ ↓ x =↓ ↓ { x } , {\displaystyle \downarrow x=\downarrow \{x\},} where upper sets and lower sets of this form are called principal. The upper closure and lower closure of a set are, respectively, the smallest upper set and lower set containing it.

The upper and lower closures, when viewed as functions from the power set of X {\displaystyle X} to itself, are examples of closure operators since they satisfy all of the Kuratowski closure axioms. As a result, the upper closure of a set is equal to the intersection of all upper sets containing it, and similarly for lower sets. (Indeed, this is a general phenomenon of closure operators. For example, the topological closure of a set is the intersection of all closed sets containing it; the span of a set of vectors is the intersection of all subspaces containing it; the subgroup generated by a subset of a group is the intersection of all subgroups containing it; the ideal generated by a subset of a ring is the intersection of all ideals containing it; and so on.)

Ordinal numbers

An ordinal number is usually identified with the set of all smaller ordinal numbers. Thus each ordinal number forms a lower set in the class of all ordinal numbers, which are totally ordered by set inclusion.